package Elementary_algorithm.Math;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
计数质数
给定整数 n ，返回 所有小于非负整数n的质数的数量 。

示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0

提示：
0 <= n <= 5 * 106
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnzlu6/
 */
public class _02计数质数 {

    @Test
    public void test() {
        System.out.println(countPrimes(10));
    }


    //方法一：枚举
    //超时
    //O(nlogn) O(n)
    public int countPrimes(int n) {

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;
    }

    public boolean isPrime(int n) {
        if (n < 2)
            return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    //官解：方法二：埃氏筛
    //O(nloglogn) O(n)
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/count-primes/solutions/507273/ji-shu-zhi-shu-by-leetcode-solution/
     */
    //ps:埃氏筛的原理：如果x是质数，那么大于x的x的倍数2x,3x,…一定不是质数；
    // 对于一个质数x，如果按上文说的我们从2x开始标记其实是冗余的，应该直接从x⋅x开始标记，
    // 因为2x,3x,…这些数一定在x之前就被其他数的倍数标记过了，例如2的所有倍数，3的所有倍数等。
    class Solution {
        public int countPrimes(int n) {
            int[] isPrime = new int[n];
            Arrays.fill(isPrime, 1);
            int ans = 0;
            for (int i = 2; i < n; ++i) {
                if (isPrime[i] == 1) {
                    ans += 1;
                    if ((long) i * i < n) {
                        for (int j = i * i; j < n; j += i) {
                            isPrime[j] = 0;
                        }
                    }
                }
            }
            return ans;
        }
    }

    //官解：方法三：线性筛
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/count-primes/solutions/507273/ji-shu-zhi-shu-by-leetcode-solution/
     */
    //ps: 埃氏筛其实还是存在冗余的标记操作,比如对于45这个数，它会同时被3,5两个数标记为合数，
    // 因此我们优化的目标是让每个合数只被标记一次，这样时间复杂度即能保证为O(n)，这就是我们接下来要介绍的线性筛
    // 相较于埃氏筛，我们多维护一个primes数组表示当前得到的质数集合。我们从小到大遍历，如果当前的数x是质数，就将其加入primes数组。
    // 另一点与埃氏筛不同的是，「标记过程」不再仅当x为质数时才进行，
    // 而是对每个整数x都进行。对于整数x，我们不再标记其所有的倍数x⋅x,x⋅(x+1),…，而是只标记质数集合中的数与x相乘的数，即x⋅primes
    class Solution2 {
        public int countPrimes(int n) {
            List<Integer> primes = new ArrayList<Integer>();
            int[] isPrime = new int[n];
            Arrays.fill(isPrime, 1);
            for (int i = 2; i < n; ++i) {
                if (isPrime[i] == 1) {
                    primes.add(i);
                }
                for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) {
                    isPrime[i * primes.get(j)] = 0;
                    if (i % primes.get(j) == 0) {
                        break;
                    }
                }
            }
            return primes.size();
        }
    }



}
